Struguri
Propusa la Bratislava. CEOI 1996
Dificultate: C3

 Imaginati-va ca mama a facut o prajitura mare ornata cu boabe de struguri. Ati 
mnca-o cu placere pe toata, dar nu se poate. Mama a decis ca poti lua numai o 
bucata, de forma rotunda, pe care o poti decupa cu gura unui pahar.
    Imagineaza-ti ca ti plac strugurii foarte mult. Stii coordonatele boabelor 
de strugure de pe prajitura si raza paharului cu care mama ti va taia o bucata. 
Problema revine la a decide ce bucata vei alege n asa fel nct sa mannci ct 
mai multe boabe de struguri.
Intrare: 
Fisierul de intrare consta din mai multe seturi de date. Prima linie a fiecarui 
set contine un numar ntreg pozitiv care contine raza paharului. A doua linie 
contine un numar ntreg pozitiv N(1N1000) care reprezinta numarul de boabe de 
strugure de pe prajitura. Urmatoarele N linii contin coordonatele fiecarui bob 
(o pereche de numere ntregi separate prin un spatiu). Nu exista doua boabe
cu aceleasi coordonate. Setul de date se termina cu o linie pe care se afla un 
numar 0.
Iesire:
Fisierul de iesire contine pentru fiecare set de date de intrare, o linie cu 
numarul maxim de boabe de strugure pe care le poti mnca de pe o bucata de 
prajitura cu raza data (boabele aflate exact pe marginea portiei se considera 
ca fiind ale tale).
Exemplu:
RAISINS.IN                           RAISINS.OUT
2                                                                      3
4
7 5
6 6
6 8
10 11
0
===================================
Solutia 1 (Ovidiu Ghiorghioiu - Alba Iulia)
{$IFDEF CPU87}
{$N+}
{$ELSE}
{$N-}
{$ENDIF}
const nmax=1000;

type setn=array[1..nmax] of integer;
     psetn=^setn;
     pint=^integer;

var t:setn;
    x,y:array[1..1000] of longint;
    l:array[1..1000] of psetn;
    nl:array[1..1000] of integer;
    i,j,k,jj,kk,n,r,a,b,c,max,nr:integer;
    dx,dy,xm,ym,xx,yy,dd:real;
    p,q:pint;
    rr,rr2:longint;
    f,g:text;

procedure citeste;
begin
     read(f,r,n);
     for i:=1 to n do read(f,x[i],y[i]);
     read(f,i);{0}
end;

procedure rezolva;
begin
     rr:=r*r;
     rr2:=rr*4;
     for i:=1 to n do begin
         k:=0;
         for j:=1 to n do
             if (i<>j) and (sqr(x[j]-x[i])+sqr(y[j]-y[i])<=rr2) then begin
                inc(k);
                t[k]:=j;
             end;
         getmem(l[i],k*2);
         move(t,l[i]^,k*2);
         nl[i]:=k;
     end;
     max:=0;
     for i:=1 to n-1 do begin
         jj:=nl[i];
         p:=@l[i]^[jj];
         while (p^>i) and (jj>0) do begin
               j:=p^;
               dec(jj);
               a:=y[i]-y[j];
               b:=x[j]-x[i];
               c:=x[i]*y[j]-y[i]*x[j];
               xm:=(x[i]+x[j])/2;ym:=(y[i]+y[j])/2;
               dd:=sqrt((rr-sqr(x[i]-xm)-sqr(y[i]-ym))/(sqr(b)+sqr(a)));
               dx:=a*dd;dy:=b*dd;
               xx:=xm-dx;yy:=ym-dy;
               q:=pint(l[i]);nr:=1;
               for kk:=1 to nl[i] do begin
                   k:=q^;
                   inc(word(q),2);
                   if (sqr(x[k]-xx)+sqr(y[k]-yy)<=rr+0.01) then inc(nr);
               end;
               if nr>max then max:=nr;
               xx:=xm+dx;yy:=ym+dy;
               q:=pint(l[i]);nr:=1;
               for kk:=1 to nl[i] do begin
                   k:=q^;
                   inc(word(q),2);
                   if (sqr(x[k]-xx)+sqr(y[k]-yy)<=rr+0.01) then inc(nr);
               end;
               if nr>max then max:=nr;
               dec(word(p),2)
         end;
         if max=n then break;
     end;
     writeln(g,max);
     for i:=1 to n do freemem(l[i],nl[i]*2);
end;

begin
     assign(f,'ceoi30.in');reset(f);
     assign(g,'ceoi30.out');rewrite(g);
     while not seekeof(f) do begin
           citeste;
           rezolva;
     end;
     close(g);
     close(f);
end.
-----------------------------------
Solutia 2 (Cristian cadar - Bucuresti)
{ REZOLVARE: Lum pe rnd cte 2 puncte si stiind raza r a cercului putem
afla centrul cercului de raza r determinat de aceste  2 puncte (vom avea 2
solutii). Apoi pt. fiecare astfel de cerc generat numr cte puncte contine.
(ca optimizare verific numai punctele care se afla la mai putin de 2*r de
cele 2 puncte considerate). Retin nr. maxim de puncte continute de un cerc.
  Complexitatea este deci O(n^3)
}
uses crt;
type
    punct=
          record
                x,y:real;
          end;
var
   p:array[1..1000] of punct;
   f:text;
   st:string;
   nr1,nr2,max,i,j,k,n:integer;
   r:real;
   c,o1,o2:punct;

procedure citire;
begin
     clrscr;
     write('Fisier intrare:');
     readln(st);
     assign(f,st);
     reset(f);
     readln(f,r);
     readln(f,n);
     for i:=1 to n do
         readln(f,p[i].x,p[i].y);
     close(f);
end;

function dist(a,b:punct):real;
begin
     dist:=sqrt( sqr(a.x-b.x) + sqr(a.y-b.y) );
end;


procedure determinare_cerc(a,b:punct);
var
   aa,bb,cc,delta,a1,b1,c1:real;
   m:punct;
   ab,om,m_ab,m_om:real;

procedure tratare_vertical;
begin
     o1.x:=m.x;
     o2.x:=m.x;
     o1.y:=m.y+om;
     o2.y:=m.y-om;
end;

begin
     { Fie A,B cele 2 puncte si M mijlocul segmentului AB. Atunci O(centrul
cercului) se afla pe dreapta OM la distanta OM care se poate calcula }
     {--}

     { Determin coordonatele punctului M }
     m.x:=(a.x+b.x)/2;
     m.y:=(a.y+b.y)/2;
     {--}

     { Calculez segmentul OM }
     ab:=dist(a,b);
     om:=sqrt( sqr(r)- sqr(ab/2) );

     {--}
     { Determin panta dreptei AB }
     if a.y=b.y
        then
            begin
                 tratare_vertical;
                 exit;
            end
        else m_om:=-(a.x-b.x)/(a.y-b.y);
     
     {--}
     { Determin O1 si O2 }
     aa:=sqr(m_om)+1;
     bb:=-2*m.x-2*sqr(m_om)*m.x;
{     cc:=sqr(m_om)+1-sqr(om);}
     cc:=- ( sqr(m_om)-sqr(m.x)*( sqr(m_om)+1 ) );
     delta:=bb*bb-4*aa*cc;
     o1.x:=( -bb+sqrt(delta) )/(2*aa);
     o1.y:=m_om*o1.x-m_om*m.x+m.y;
     {-}
     o2.x:=(-bb-sqrt(delta) )/(2*aa);
     o2.y:=m_om*o2.x-m_om*m.x+m.y;
end;

procedure generare;
begin
     max:=0;
     for i:=1 to n do
         for j:=1 to n do
             if (i<>j) and (dist(p[i],p[j])<=2*r)
                then
                    begin
                         nr1:=0;
                         nr2:=0;
                         determinare_cerc(p[i],p[j]);
                         for k:=1 to n do
                             begin
                                  if dist(o1,p[k])<=r
                                     then inc(nr1);
                                  if dist(o2,p[k])<=r
                                     then inc(nr2);
                             end;
                         if nr1>max
                            then
                                begin
                                     max:=nr1;
                                     c:=o1;
                                end;
                         if nr2>max
                            then
                                begin
                                     max:=nr2;
                                     c:=o2;
                                end;
                    end;
end;

procedure afis;
begin
     writeln('Nr. maxim de boabe:',max);
     writeln('Coordonatele centrului: (',c.x:6:2,',',c.y:6:2,')');
     readkey;
end;

begin
     citire;
     generare;
     afis;
end.
-------------------------------
Solutia 3 (Mihai stroe)
{ REZOLVARE: Lum pe rnd cte 2 puncte si stiind raza r a cercului putem
afla centrul cercului de raza r determinat de aceste  2 puncte (vom avea 2
solutii). Apoi pt. fiecare astfel de cerc generat numr cte puncte contine.
(ca optimizare verific numai punctele care se afla la mai putin de 2*r de
cele 2 puncte considerate). Retin nr. maxim de puncte continute de un cerc.
  Complexitatea este deci O(n^3)
}
uses crt;
type
    punct=
          record
                x,y:real;
          end;
var
   p:array[1..1000] of punct;
   f:text;
   st:string;
   nr1,nr2,max,i,j,k,n:integer;
   r:real;
   c,o1,o2:punct;

procedure citire;
begin
     clrscr;
     write('Fisier intrare:');
     readln(st);
     assign(f,st);
     reset(f);
     readln(f,r);
     readln(f,n);
     for i:=1 to n do
         readln(f,p[i].x,p[i].y);
     close(f);
end;

function dist(a,b:punct):real;
begin
     dist:=sqrt( sqr(a.x-b.x) + sqr(a.y-b.y) );
end;


procedure determinare_cerc(a,b:punct);
var
   aa,bb,cc,delta,a1,b1,c1:real;
   m:punct;
   ab,om,m_ab,m_om:real;

procedure tratare_vertical;
begin
     o1.x:=m.x;
     o2.x:=m.x;
     o1.y:=m.y+om;
     o2.y:=m.y-om;
end;

begin
     { Fie A,B cele 2 puncte si M mijlocul segmentului AB. Atunci O(centrul
cercului) se afla pe dreapta OM la distanta OM care se poate calcula }
     {--}

     { Determin coordonatele punctului M }
     m.x:=(a.x+b.x)/2;
     m.y:=(a.y+b.y)/2;
     {--}

     { Calculez segmentul OM }
     ab:=dist(a,b);
     om:=sqrt( sqr(r)- sqr(ab/2) );

     {--}
     { Determin panta dreptei AB }
     if a.y=b.y
        then
            begin
                 tratare_vertical;
                 exit;
            end
        else m_om:=-(a.x-b.x)/(a.y-b.y);
     
     {--}
     { Determin O1 si O2 }
     aa:=sqr(m_om)+1;
     bb:=-2*m.x-2*sqr(m_om)*m.x;
{     cc:=sqr(m_om)+1-sqr(om);}
     cc:=- ( sqr(m_om)-sqr(m.x)*( sqr(m_om)+1 ) );
     delta:=bb*bb-4*aa*cc;
     o1.x:=( -bb+sqrt(delta) )/(2*aa);
     o1.y:=m_om*o1.x-m_om*m.x+m.y;
     {-}
     o2.x:=(-bb-sqrt(delta) )/(2*aa);
     o2.y:=m_om*o2.x-m_om*m.x+m.y;
end;

procedure generare;
begin
     max:=0;
     for i:=1 to n do
         for j:=1 to n do
             if (i<>j) and (dist(p[i],p[j])<=2*r)
                then
                    begin
                         nr1:=0;
                         nr2:=0;
                         determinare_cerc(p[i],p[j]);
                         for k:=1 to n do
                             begin
                                  if dist(o1,p[k])<=r
                                     then inc(nr1);
                                  if dist(o2,p[k])<=r
                                     then inc(nr2);
                             end;
                         if nr1>max
                            then
                                begin
                                     max:=nr1;
                                     c:=o1;
                                end;
                         if nr2>max
                            then
                                begin
                                     max:=nr2;
                                     c:=o2;
                                end;
                    end;
end;

procedure afis;
begin
     writeln('Nr. maxim de boabe:',max);
     writeln('Coordonatele centrului: (',c.x:6:2,',',c.y:6:2,')');
     readkey;
end;

begin
     citire;
     generare;
     afis;
end.
------------------------------
Solutia 4 (Ovidiu Ghiorghioiu)
{$IFDEF CPU87}
{$N+}
{$ELSE}
{$N-}
{$ENDIF}
const nmax=1000;

type setn=array[1..nmax] of integer;
     psetn=^setn;
     pint=^integer;

var t:setn;
    x,y:array[1..1000] of longint;
    l:array[1..1000] of psetn;
    nl:array[1..1000] of integer;
    i,j,k,jj,kk,n,r,a,b,c,max,nr:integer;
    dx,dy,xm,ym,xx,yy,dd:real;
    p,q:pint;
    rr,rr2:longint;
    f,g:text;

procedure citeste;
begin
     read(f,r,n);
     for i:=1 to n do read(f,x[i],y[i]);
     read(f,i);{0}
end;

procedure rezolva;
begin
     rr:=r*r;
     rr2:=rr*4;
     for i:=1 to n do begin
         k:=0;
         for j:=1 to n do
             if (i<>j) and (sqr(x[j]-x[i])+sqr(y[j]-y[i])<=rr2) then begin
                inc(k);
                t[k]:=j;
             end;
         getmem(l[i],k*2);
         move(t,l[i]^,k*2);
         nl[i]:=k;
     end;
     max:=0;
     for i:=1 to n-1 do begin
         jj:=nl[i];
         p:=@l[i]^[jj];
         while (p^>i) and (jj>0) do begin
               j:=p^;
               dec(jj);
               a:=y[i]-y[j];
               b:=x[j]-x[i];
               c:=x[i]*y[j]-y[i]*x[j];
               xm:=(x[i]+x[j])/2;ym:=(y[i]+y[j])/2;
               dd:=sqrt((rr-sqr(x[i]-xm)-sqr(y[i]-ym))/(sqr(b)+sqr(a)));
               dx:=a*dd;dy:=b*dd;
               xx:=xm-dx;yy:=ym-dy;
               q:=pint(l[i]);nr:=1;
               for kk:=1 to nl[i] do begin
                   k:=q^;
                   inc(word(q),2);
                   if (sqr(x[k]-xx)+sqr(y[k]-yy)<=rr+0.01) then inc(nr);
               end;
               if nr>max then max:=nr;
               xx:=xm+dx;yy:=ym+dy;
               q:=pint(l[i]);nr:=1;
               for kk:=1 to nl[i] do begin
                   k:=q^;
                   inc(word(q),2);
                   if (sqr(x[k]-xx)+sqr(y[k]-yy)<=rr+0.01) then inc(nr);
               end;
               if nr>max then max:=nr;
               dec(word(p),2)
         end;
         if max=n then break;
     end;
     writeln(g,max);
     for i:=1 to n do freemem(l[i],nl[i]*2);
end;

begin
     assign(f,'ceoi30.in');reset(f);
     assign(g,'ceoi30.out');rewrite(g);
     while not seekeof(f) do begin
           citeste;
           rezolva;
     end;
     close(g);
     close(f);
end.
----------------------------------
